import random

# 双向链表的python实现
class Node:
    def __init__(self,item):
        self.item=item
        self.nextNode=None
        self.prevNode=None
    
class doubleLinklist:
    def __init__(self,node):
        if isinstance(node,Node):
            self.__head=node
        else:
            self.__head=None
    def isEmpty(self):
        # 判断链表是否为空
        return self.__head==None
    def linkLength(self):
        # 链表长度
        count=0
        indexHead=self.__head
        while indexHead!=None:
            count+=1
            indexHead=indexHead.nextNode
        return count
    def linkTravel(self):
        # 遍历整个链表
        indexHead=self.__head
        while indexHead!=None:
            print(indexHead.item,end='\t')
            indexHead=indexHead.nextNode
        print()
    def linkAdd(self,item):
        # 链表头部添加元素
        indexHead=self.__head
        newNode=Node(item)
        if indexHead==None:
            self.__head=newNode
            
        else:
            newNode.nextNode=indexHead
            indexHead.prevNode=newNode
            self.__head=newNode
    def linkAppend(self,item):
        # 链表尾部添加元素
        indexHead=self.__head
        newItem=Node(item)
        if indexHead==None:
            self.__head=newItem
        else:
            while indexHead.nextNode!=None:
                indexHead=indexHead.nextNode
            indexHead.nextNode=newItem
            newItem.prevNode=indexHead
    def linkInsert(self,pos,item):
        # 向链表中插入元素
        indexHead=self.__head
        newNode=Node(item)
        # 链表为空头节点结尾要插入的节点
        if indexHead==None:
            self.__head=newNode
        # 插入位置为0，或者为负，直接作为头节点插入
        elif pos<=0:
            self.linkAdd(item)
        # 插入位置大于整个链表的索引，直接尾部插入
        elif pos>(self.linkLength()-1):
            self.linkAppend(newNode)
        # 正常插入
        else:
            count=1
            while count<pos:
                indexHead=indexHead.nextNode
                count+=1
            newNode.nextNode=indexHead.nextNode
            newNode.prevNode=indexHead
            indexHead.nextNode=newNode
    def linkRemove(self,item):
        # 链表中删除元素
        indexHead=self.__head
        prevNode=self.__head
        if indexHead==None:
            print("整个链表为空，不需删除")
            return
        else:
            while indexHead!=None and indexHead.item!=item:
                prevNode=indexHead
                indexHead=indexHead.nextNode
            # 如果要删除的是头节点
            if self.__head.item==item:
                self.__head=self.__head.nextNode
                self.__head.prevNode=None

            # 如果要删除的是最后一个节点
            elif indexHead.nextNode==None:
                prevNode.nextNode=None
            
            # 不是最后一个节点
            else:
                prevNode.nextNode=indexHead.nextNode
                indexHead.nextNode.prevNode=prevNode

    def linkSearch(self,item):
        # 查找链表中的一个节点是否存在
        indexHead=self.__head
        if indexHead==None:
            return False
        else:
            while indexHead!=None:
                if indexHead.item==item:
                    return True
                indexHead=indexHead.nextNode
            return False

if __name__=="__main__":
    myList=doubleLinklist(Node(10))
    myList.linkAdd(20)
    myList.linkAdd(21)
    myList.linkAppend(30)
    myList.linkAppend(31)
    myList.linkTravel()
    myList.linkInsert(3,40)
    myList.linkInsert(3,41)
    myList.linkTravel()
    myList.linkRemove(20)
    myList.linkRemove(21)
    myList.linkRemove(31)
    myList.linkTravel()
    print(myList.linkSearch(41))